home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / d2_dictionary.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  4.5 KB  |  110 lines
  1. {\magonebf  6.2 Two-dimensional dictionaries (d2\_dictionary)}
  2.  
  3. \declthree d2\_dictionary K1 K2 I
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $D$ of the parameterized data type \name\ is a 
  8. collection of items ($dic2\_item$). Every item in $D$ contains a key from the 
  9. linearly ordered data type $K1$, a key from the linearly ordered data type $K2$,
  10. and an information from data type $I$. $K1$ and $K2$ are called the key types 
  11. of $D$, and $I$ is called the information type of $D$. The number
  12. of items in $D$ is called the size of $D$. A two-dimensional dictionary of size
  13. zero is said to be  empty. We use $<k_1,k_2,i>$ to denote the item with first 
  14. key $k_1$, second key $k_2$, and information $i$. For each pair 
  15. $(k_1,k_2) \in K1 \times K2$ there is at most one item $<k_1,k_2,i> \in D$.
  16. Additionally to the normal dictionary operations, the data type $d2\_dictionary$
  17. supports rectangular range queries on $K1\times K2$.
  18.  
  19.  
  20.  
  21. \bigskip
  22. {\bf 2. Creation}
  23.  
  24. \create D {}
  25.  
  26. creates an instance \var\ of type \name\ and initializes \var\ to the 
  27. empty dictionary. 
  28.  
  29.  
  30.  
  31. \bigskip
  32. {\bf 3. Operations}
  33.  
  34. \+\cleartabs & \hskip 3truecm & \hskip 5truecm &\cr
  35. \+\op K1               key1 {dic2\_item\ it}  
  36.                             {returns the first key of item $it$.}
  37. \+\nop                      {\precond $it$ is an item in \var.}
  38. \smallskip
  39. \+\op K2               key2 {dic2\_item\ it}  
  40.                             {returns the second key of item $it$.}
  41. \+\nop                      {\precond $it$ is an item in \var.}
  42. \smallskip
  43. \+\op I                inf {dic2\_item\ it}   
  44.                             {returns the information of item $it$.}
  45. \+\nop                      {\precond $it$ is an item in \var.}
  46. \smallskip
  47. \+\op dic2\_item       max\_key1 {}   
  48.                             {returns the item with maximal first key.}
  49. \smallskip
  50. \+\op dic2\_item       max\_key2 {}   
  51.                             {returns the item with maximal second key.}
  52. \smallskip
  53. \+\op dic2\_item       min\_key1 {}   
  54.                             {returns the item with minimal first key.}
  55. \smallskip
  56. \+\op dic2\_item       min\_key2 {}   
  57.                             {returns the item with minimal second key.}
  58. \smallskip
  59. \+\op dic2\_item       insert {K1\ k_1,\ K2\ k_2,\ I\ i}  {}
  60. \+\nop                      {associates the information $i$ with the keys}
  61. \+\nop                      {$k_1$ and $k_2$. If there is an item $<k_1,k_2,j>$}
  62. \+\nop                      {in \var\ then $j$ is replaced by i, else a new }
  63. \+\nop                      {item $<k_1,k_2,i>$ is added to $D$. In both }
  64. \+\nop                      {cases the item is returned.}
  65. \smallskip
  66. \+\op dic2\_item       lookup {K1\ k_1,\ K2\ k_2}  {}
  67. \+\nop                      {returns the item with keys $k_1$ and $k_2$}
  68. \+\nop                      {(nil if no such item exists in \var).}
  69. \smallskip
  70. \+\op list\<dic2\_item\> range\_search {K1\ a,\ K1\ b,\ K2\ c,\ K2\ d} {}
  71. \+\nop                      {returns the list of all items $<k_1,k_2,i> \in$ \var} 
  72. \+\nop                      {with $a \le k_1 \le b$ and $c \le k_2 \le d$.}
  73. \smallskip
  74. \+\op list\<dic2\_item\> all\_items {}
  75.                             {returns the list of all items of \var.}
  76. \smallskip
  77. \+\op void             del {K1\ k_1,\ K2\ k_2}         
  78.                             {deletes the item with keys $k_1$ and $k_2$}
  79. \+\nop                      {from \var.}
  80. \smallskip
  81. \+\op void             del\_item {dic2\_item\ it}   
  82.                             {removes item $it$ from \var.}
  83. \+\nop                      {\precond $it$ is an item in \var.}
  84. \smallskip
  85. \+\op void             change\_inf {dic2\_item\ it,\ I\ i} {}
  86. \+\nop                      {makes $i$ the information of item $it$.}
  87. \+\nop                      {\precond $it$ is an item in \var.}
  88. \smallskip
  89. \+\op void             clear {}           
  90.                             {makes \var\ the empty d2\_dictionary.}
  91. \smallskip 
  92. \+\op bool             empty {}           
  93.                             {returns true if \var\ is empty, false otherwise.}
  94. \smallskip 
  95. \+\op int  size {}          
  96.                             {returns the size of \var.}
  97.  
  98.  
  99.  
  100. \bigskip
  101. {\bf 4. Implementation}
  102.  
  103. Two-dimensional dictionaries are implemented by dynamic two-dimensional range
  104. trees [Wi85, Lu78] based on BB[$\alpha$] trees. Operations insert, lookup, 
  105. del\_item, del take time $O(\log^2 n)$,  range\_search takes time 
  106. $O(k + \log^2 n)$, where $k$ is the size of the returned list, key, inf, 
  107. empty, size, change\_inf take time $O(1)$, and clear takes time $O(n\log n)$.
  108. Here $n$ is the current size of the dictionary. The space requirement is 
  109. $O(n\log n)$.
  110.